class H_MAP{K,E} < $MAP{K,E}

****	Hash table based on data buckets Make public

---

Ancestors

$MAP{_,_}	$RO_MAP{_,_}	$STR	$CONTAINER{_}
$ELT{_}	$ELT	MAP_INCL{_,_}	COMPARE{_}

Descendants

MAP{_,_}

---

Public

Features

map_aget(k:K): E .. Included as aget

****	Returns the element equal to 'e' from the set. Returns void or T::nil if there is no such element. Self may not be void.

map_aset(k:K,e:E) .. Included as aset

****	Over-ride data if 'k' exists. Otherwise grow the bucket chain associated with hash(k)

map_copy: SAME .. Included as copy

****	Returns a copy of self with all properties set like self.

count(v:ETP):INT .. Included as count

****	The number of elements that are `elt_eq' to `v'. Self may be void.

count_if( test:ROUT{ETP}:BOOL ):INT .. Included as count_if

****	The number of elements which satisfy `test'. Self may be void.

create: SAME .. Included as create

delete(k:K)

map_delete(k:K): E .. Included as delete

****	Removes an element from the set. Does nothing if there is no such element.

elt_eq(e1,e2:ETP):BOOL .. Included as elt_eq

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_hash(e:ETP):INT .. Included as elt_hash

****	A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants.

elt_lt(e1,e2:ETP):BOOL .. Included as elt_lt

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_nil: ETP .. Included as elt_nil

****	Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void _

elt_str: STR .. Included as elt_str

****	Prints out a string version of the array of the components that are under $STR, and their associated indices

equals(e: $RO_MAP{ITP,ETP}): BOOL .. Included as equals

****	Returns true if all of "e"'s elements are equal to self's elts Ordering is an issue. Should be redefined to be more precise for particular descendants

every( test:ROUT{ETP}:BOOL ):BOOL .. Included as every

****	True if every element of self satisfies `test'. Self may be void.

has(e: ETP): BOOL .. Included as has

has_elt(e:ETP):BOOL .. Included as has_elt

****	True if the self has an element which is `elt_eq' to `e'.

map_has_ind(k:K): BOOL .. Included as has_ind

inds: ARRAY{ITP} .. Included as inds

****	Return an index array which is the same size as self and is set to the values of the indices

is_elt_nil(e:ETP):BOOL .. Included as is_elt_nil

map(r:ROUT{ETP}:ETP) .. Included as map

****	Set each element of self to the result of applying `r' to it.

notany( test:ROUT{ETP}:BOOL ):BOOL .. Included as notany

****	True if none of the elements of self satisfies `test'. Self may be void.

notevery( test:ROUT{ETP}:BOOL ):BOOL .. Included as notevery

****	True if not every element of self satisfies `test'. Self may be void.

permute_into( new_pos :$RO_MAP{ITP,ITP}, destination: $MAP{ITP,ETP}) .. Included as permute_into

****	Copy the entries from orig_arr into self using the permutation array "new_positions"

replace(o,n:ETP) .. Included as replace

****	Replace elements that are `elt_eq' to `o' by `n' wherever it occurs

replace_if(test:ROUT{ETP}:BOOL, n:ETP) .. Included as replace_if

****	Replace elements that satisfy `test' by `n'.

size: INT

some( test:ROUT{ETP}:BOOL ):BOOL .. Included as some

****	True if some element of self satisfies `test'. Self may be void.

str: STR .. Included as str

****	Prints out a string version of the array of the components that are under $STR, and their associated indices

test_if(test:ROUT{ETP}:BOOL,out ind: ITP, out elt: ETP):BOOL .. Included as test_if

****	Return true if an element satisfies test "test" Arg "ind" is set to the index of the element satisfying "test" Arg "elt" is set to the element satisfying "test"

Iters

map_elt!: E .. Included as elt!

map_key!: K .. Included as ind!

map_pair!: TUP{K,E} .. Included as pair!

---

Private

attr asize: INT; .. Included as asize

****	The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal.

attr asize: INT; .. Included as asize

****	The size of the fraction of the store which is currently in use. Array access beyond this bound is illegal.

attr bound: INT; .. Included as bound

****	Upper bound for split_pos. Is always initial_size * 2.pow(doubles)

attr bound: INT; .. Included as bound

****	Upper bound for split_pos. Is always initial_size * 2.pow(doubles)

bucket(i:INT): BUCKET .. Included as bucket

create_sized(initial_size:INT): SAME .. Included as create_sized

****	Creating a table with another minimal size. This might be useful to avoid shrinking of large table which might get very empty.

data_nil: E .. Included as data_nil

dbg: STR .. Included as dbg

****	Returns an interal string representation of the hashtable. For debugging only.

attr doubles: INT; .. Included as doubles

****	Number of times the initial table size has been doubled.

attr doubles: INT; .. Included as doubles

****	Number of times the initial table size has been doubled.

elt_eq(e1,e2:ETP):BOOL .. Included as elt_key_eq

****	The "less than" relation used in the sorting routines. Compares the object "id" by default. May be redefined in descendants.

elt_hash(e:ETP):INT .. Included as elt_key_hash

****	A hash value associated with an element. Must have the property that if "elt_eq(e1,e2)" then "elt_hash(e1)=elt_hash(e2)". Can be defined to always return 0, but many routines will then become quadratic. Uses object "id" by default. May be redefined in descendants.

elt_nil: ETP .. Included as elt_key_nil

****	Return the nil value. If the element is under $NIL then return e.nil. Otherwise, return void _

elt_str(e: ETP): STR .. Included as elt_str

grow .. Included as grow

****	Increases the size of the array by one. The functions changing the size of the bucket table: They are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow)

hash(e:E): INT .. Included as hash

****	Returns the bucket to store e. This number will be generated from the hash-value and be normailzed through the actual size of the set.

ind_str(i: ITP): STR .. Included as ind_str

shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio

shared lower_fill_ratio: FLT := 0.800; .. Included as lower_fill_ratio

attr minsize: INT; .. Included as minsize

****	Lower bound for the store size.

attr minsize: INT; .. Included as minsize

****	Lower bound for the store size.

attr n_inds: INT; .. Included as n_inds

****	Returns the number of elements (resp. indices) in the table.

attr n_inds: INT; .. Included as n_inds

****	Returns the number of elements (resp. indices) in the table.

set_bucket(i:INT,l:BUCKET) .. Included as set_bucket

shrink .. Included as shrink

****	Decreases the size of the array by one. Resizes the storage area, if neccessary.

attr split_pos: INT; .. Included as split_pos

****	Position of the next bucket to split.

attr split_pos: INT; .. Included as split_pos

****	Position of the next bucket to split.

attr store: AREF{BUCKET}; .. Included as store

****	Here is the data being stored.

attr store: AREF{BUCKET}; .. Included as store

****	Here is the data being stored.

update_delete .. Included as update_delete

****	Checks the actual fill ratio of the set. Removes a bucket from the hash table if the ratio is low enough.

update_insert .. Included as update_insert

****	Checks the actual fill ratio of the set. Adds a bucket to the hash table if the ratio is high enough. The functions changing the size of the bucket table are split into two parts. 1.) Splitting the next bucket into two. (update_*) 2.) Resizing the storage area. (shrink/grow)

shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio

****	For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.)

shared upper_fill_ratio: FLT := 1.000; .. Included as upper_fill_ratio

****	For fast access one needs a low ratio between number of elements in the and number of cells. For efficient memory usage one needs a high ratio. The ratio should always be between these two bounds (unless the table is really small; where the ratio can get even lower.)

---

The Sather Home Page

---